Binary adder networks are basic to digital computer arithmetic operation. Because of the large number of adder operations involved, the history of computer development shows a constant search for faster adder networks either through faster component technology or by improved network organization using various auxiliary logic or computing networks to augment the basic adder unit.
Early digital computers used ripple-carry adders in which the i.sup.th adder output bit may be represented by the modulo-2 bit sum EQU S.sub.i =A.sub.i .sym.B.sub.i .sym.C.sub.i-1
where A.sub.i and B.sub.i are the i.sup.th bit of the input operands, and C.sub.i-1 is the carry-in from the next lowest bit sum. The carry-in may be represented in terms of the prior stage operands (A.sub.i-1, B.sub.i-1) and the prior stage carry-in, C.sub.i-2, as C.sub.i-1 =A.sub.i-1 *B.sub.i-1 +C.sub.i-2 (A.sub.i-1 +B.sub.i-1) where (*,+) are Boolean (AND, OR) operators respectively. The time for the carry-bits to ripple through became the limiting factor in the speed of adders. Subsequent fixed-time adders were introduced to overcome these deficiencies. These fixed-time adders may be classified into two categories: conditional sum and carry-look-ahead (CLA) adders.
Conditional adders compute each bit sum, S.sub.i, twice: one sum, S.sub.Ni, based on the assumption that the carry-in bit, C.sub.i, is zero; a second sum, S.sub.Ei, on the assumption that C.sub.i =1. FIG. 1 is the logic diagram of a 4-bit-slice conditional sum adder. (Ref. "Introduction to Arithmetic", Waser and Flynn, Holt, Rinehart and Winston, 1982, p. 77ff). The two input operands are represented by input bits A.sub.0, A.sub.1, A.sub.2, A.sub.3 and B.sub.0, B.sub.1, B.sub.2, B.sub.3, respectively. Each pair of operand bits (A.sub.i, B.sub.i) are applied to input terminals 110. A.sub.0, B.sub.0 correspond to the input operand least significant bit while A.sub.3, B.sub.3 correspond to the most significant bits. The conditional sum adder consists of two basic sections: the conditional sum generator unit 130 that forms at its output the two sets of conditional sums and conditional carry, S.sub.N0, S.sub.N1, S.sub.N2, S.sub.N3, C.sub.N4 and S.sub.E0, S.sub.E1, S.sub.E2, S.sub.E3, C.sub.E4, the latter group being based on the assumption of a non-zero carry-in to its corresponding individual conditional sum generator 141, 143, 145, 147, 149, respectively. These conditional signals are applied to conditional sum selector unit 150 consisting of the individual output selectors 161, 163, 165, 167, 169 corresponding to output sum bits S.sub.0, S.sub.1, S.sub.2, S.sub.3 and output carry bit C4. The selection is controlled by the carry-in bit, C.sub.0, and its complement, C.sub.0, operating on the conditional sums by means of AND-gates 113 and OR-gates 115.
The logic equations governing the behavior of the conditional 4-bit slice adder of FIG. 1 are as follows: EQU S.sub.N0 =A.sub.0 .sym.B.sub.0 EQU S.sub.E0 =S.sub.N0 EQU S.sub.N1 =A.sub.1 .sym.B.sub.1 .sym.G.sub.0 EQU S.sub.E1 =A.sub.1 .sym.B.sub.1 .sym.P.sub.0 EQU S.sub.N2 =A.sub.2 .sym.B.sub.2 .sym.(G.sub.1 +T.sub.1 G.sub.0) EQU S.sub.E2 =A.sub.2 .sym.B.sub.2 .sym.(G.sub.1 +T.sub.1 P.sub.0) EQU S.sub.N3 =A.sub.3 .sym.B.sub.3 .sym.(G.sub.2 +T.sub.2 G.sub.1 +T.sub.2 T.sub.1 G.sub.0) EQU S.sub.E3 =A.sub.3 .sym.B.sub.3 .sym.(G.sub.2 +T.sub.2 G.sub.1 +T.sub.2 T.sub.1 P.sub.0) EQU C.sub.N4 =G.sub.3 +T.sub.3 G.sub.2 +T.sub.3 T.sub.2 G.sub.1 +T.sub.3 T.sub.2 T.sub.1 G.sub.0 EQU C.sub.E4 =G.sub.3 +T.sub.3 G.sub.2 +T.sub.3 T.sub.2 G.sub.1 +T.sub.3 T.sub.2 T.sub.1 P.sub.0
where
G.sub.i =A.sub.i B.sub.i,
P.sub.i =A.sub.i B.sub.i,
T.sub.i =A.sub.i .sym.B.sub.i.
The true 4-bit sum and carry-out is selected by selector unit 150 in accordance in accordance with the following boolean equations: EQU S.sub.0 =S.sub.E0 C.sub.0 +S.sub.N0 C.sub.0 EQU S.sub.1 =S.sub.E1 C.sub.0 +S.sub.N1 C.sub.0 EQU S.sub.2 =S.sub.E2 C.sub.0 +S.sub.N2 C.sub.0 EQU S.sub.3 =S.sub.E3 C.sub.0 +S.sub.N3 C.sub.0 EQU C.sub.4 =C.sub.E4 C.sub.0 +C.sub.N4
The above concept could be extended to additional bits with the attendant increase in complexity implied by the above equations and by FIG. 1.
Carry-looks ahead (CLA) adders have been the most popular integrated circuit implementation in the recent past because of their simplicity and modularity. Modularity implies relative ease in extending the number of bits in each operand by the use of identical parallel units.
Consider, for example, the 4-bit slice CLA of FIG. 2. Comparison with FIG. 1, a 4-bit slice conditional adder, clearly shows the relative simplicity of the CLA.
The CLA sum may be expressed in the following logic expression as EQU S.sub.i =A.sub.i .sym.B.sub.i .sym.C.sub.i-1, i=0, 1, 2, 3
and the CLA carry as EQU C.sub.i +A.sub.i B.sub.i +C.sub.i (A.sub.i +B.sub.i)
or EQU C.sub.i =G.sub.i +P.sub.i C.sub.i
where EQU G.sub.i =A.sub.i B.sub.i
and EQU P.sub.i =A.sub.i +B.sub.i
The above CLA sum expression can be immediately evaluated, absent the carry term (C.sub.i-1), by forming the EOR of the two operands (A.sub.i, B.sub.i). The carry term, C.sub.i-1, is a function of lower order indexed operands, (A.sub.i-1, B.sub.i-1), and lower order carries, C.sub.i-2. As a result, the time to complete an addition is generally governed by availability of the carry-in bit to each sum-bit.
The above expression for C.sub.i is a recursive equation, i.e., one in which the current value, C.sub.i+1, is a function of its own past values. It may be explicitly stated as follows: EQU C.sub.i+1 =G.sub.i +P.sub.i G.sub.i-1 +P.sub.i P.sub.i-1 G.sub.i-2 + . . . +P.sub.i P.sub.i-1 . . . P.sub.0 C.sub.0
Hence, for the four-bit case of FIG. 2, the major output carry, C4, may be expressed as EQU C.sub.4 =G.sub.3 +P.sub.3 G.sub.2 +P.sub.3 P.sub.2 G.sub.1 +P.sub.3 P.sub.2 P.sub.1 G.sub.0 +P.sub.3 P.sub.2 P.sub.1 P.sub.0 C.sub.0
By substituting the following into the above expression EQU G.sub.0 '=G.sub.3 +P.sub.3 G.sub.2 +P.sub.3 P.sub.2 G.sub.1 +P.sub.3 P.sub.2 P.sub.1 G.sub.0
and P.sub.0 '=P.sub.3 P.sub.2 P.sub.1 P.sub.0 C.sub.0 obtains C.sub.4 =G.sub.0 '+P.sub.0 'C.sub.0 which represents the logical expression for the G.sub.0 ',P.sub.0 ' output terminals of FIG. 2.
If two networks of the type shown in FIG. 2 were to be used as a modular units for generating an 8-bit sum, the carry-in bit to the higher order 4-bit network, C4, would have to be formed in accordance with the above expression. The output carry of the higher order unit, C8, would then be expressible as EQU C.sub.8 =G.sub.1 '+P.sub.1 'G.sub.0 '+P.sub.1 'P.sub.0 'C.sub.0
where G'.sub.1 and P'.sub.1 are the CLA output pair of the next higher order CLA modular unit.
Modularity was extended by means of a four group CLA generator that accommodated four CLA 4-bit slice adders and produced at output the necessary carry information, i.e., C.sub.4, C.sub.8, C.sub.12 and P", G", to form a 16-bit CLA adder using four modular adder units of the type shown in FIG. 2. FIG. 3 shows a four group CLA generator with four input pairs, (G'.sub.0,P'.sub.0), (G'.sub.1,P'.sub.1), (G'.sub.2,P'.sub.2) and (G'.sub.3,P'.sub.3) and carry outputs corresponding to C.sub.4, C.sub.8, C.sub.12 and (P", G"), where EQU G.sub.12 =G'.sub.2 +P'.sub.2 G'.sub.1 +P'.sub.2 P'.sub.1 G'.sub.0 +P'.sub.2 P'.sub.1 P'.sub.0 C.sub.0
and EQU G"=G'.sub.3 +P'.sub.3 G'.sub.2 +P'.sub.3 P'.sub.2 P'.sub.1 C.sub.0 EQU P"=P'.sub.3 P'.sub.2 P'.sub.1 P'.sub.0
Thus, the most significant carry-out bit, C16, could be logically formed as EQU C.sub.16 =G"+P"C.sub.0
and passed on, as needed, to higher order modular CLA adder units.
FIG. 4 shows the logical extension of modular CLA concept to 64-bit addition. A total of sixteen modular 4-bit slice SLA adders 200 are arrayed in parallel to accept input operand pairs, (A.sub.0, B.sub.0) . . . (A.sub.3, B.sub.3), (A.sub.4, B.sub.4) . . . (A.sub.7, B.sub.7), . . . , (A.sub.60, B.sub.60) . . . (A.sub.63, B.sub.63) and carry-in bits, (C.sub.0, C.sub.16, C.sub.32, C.sub.48), each producing 4-bit output sums, (S.sub.0, S.sub.1, S.sub.3) . . . (S.sub.60, S.sub.61, S.sub.62, S.sub.63) and carry-generate/carry-propagate pairs (P'.sub.0,G'.sub.0), . . . (P'.sub.15,G'.sub.15).
A second logical level of four modular four group CLA generators 250, each accepting the carry output information of a corresponding group of four CLA adders 200, generates the necessary carry information for its associated adders 200 from the four pairs of carry-generate/carry-propagate pairs and the necessary carry-generate/carry-propagate pairs, [(P".sub.0,G".sub.0), (P".sub.1,G".sub.1), and (P".sub.2,G".sub.2)], from which the third logic level consisting of a single CLA generator 250 generates the three additional carry-in bits, (C.sub.16, C.sub.32, C.sub.48) supplied to the first and second levels. In this manner, modular 4-bit slice CLA adders have been used to accommodate higher precision operation.
Also, the basic conditional adder unit of FIG. 1 may be used as a modular adder and extended to higher precision addition by using the CLA generator concept because the logic equations defining the higher order carries are similar. For example, it may be shown (op cit Waser and Flynn) that the second level conditional same carries may be expressed as EQU C.sub.4 =C.sub.N4 +C.sub.E4 C.sub.0 EQU C.sub.8 =C.sub.N8 +C.sub.E8 C.sub.N4 +C.sub.E8 C.sub.E4 C.sub.0 EQU C.sub.12 =C.sub.N12 +C.sub.E12 C.sub.N8 +C.sub.E12 C.sub.E8 C.sub.N8 +C.sub.E12 C.sub.E8 C.sub.E4 C.sub.0
Because the logic required to implement the above expressions is identical to that of the CLA generator 250 of FIG. 3 and 4, a 16-bit adder may be implemented as shown in FIG. 5. The adder has four conditional adders 100 connected in parallel, each accepting 4-bit pairs of operands. Each adder 100 consists of a conditional sum generator 130 and a multiplexor 150. The modular group carry-out pairs, [(C.sub.N4, C.sub.E4), (C.sub.N8, C.sub.E8), (C.sub.N12, C.sub.E12)], are supplied to CLA generator 250 which produces the modular carry-in bits (C4, C8, C12) required to form the sixteen bit addition. The extension required to accommodate more bits clearly indicated by the CLA method previously discussed.
Because of the need for cost effective parallel fast adders, it is highly desirable that the number of processing steps required to generate the carry-bits (and hence the sum) be proportional to the logarithm of the number of bits in each operand, and at a relatively low-cost. Also, a logic structure that allows constant fan-in and fan-out and permits static versus fixed rate pre-charge/discharge operation is desirable. The present invention is designed to achieve these goals.